// https://www.lintcode.com/problem/copy-books/description

// class Solution {
// public:
//     /**
//      * @param pages: an array of integers
//      * @param k: An integer
//      * @return: an integer
//      */
//     int copyBooks(vector<int> &pages, int k) {
// // Input
// // []
// // 1
// // Output
// // 2147483647
// // Expected
// // 0
//         int n = pages.size();
//         if (n == 0) return 0;
//         if (k > n) k = n; //优化时间复杂度！
//         vector<vector<int>> ans(k + 1, vector<int>(n + 1, INT_MAX)); //前k个人抄前n本书
//         for (int i = 0; i < k + 1; ++i)
//             ans[i][0] = 0; 
//         // ans[0][0] = 0; 只初始化ans[0][0]也可以，但上面思路更清楚一些
//         for (int t = 1; t < k + 1; ++t)
//         {
//             for (int i = 1; i < n + 1; ++i)
//             {
//                 int sum = 0;
//                 // for (int j = 0; j < i; ++j)
//                 // {
//                 //     sum += pages[j];
//                 // }
//                 // for (int j = 0; j <= i; ++j)
//                 // {
//                     // if (j > 0) sum -= pages[j - 1];

//                 for (int j = i; j >= 0; --j)
//                 {
//                     ans[t][i] = min(ans[t][i], max(ans[t - 1][j], sum)); 
//                     if (j > 0) sum += pages[j - 1];
//                 }
//             }
//         }
//         return ans[k][n];
//     }
// };

// 法二：二分法，限定时间，每个人分到不能再抄为止
class Solution {
public:
//     /**
//      * @param pages: an array of integers
//      * @param k: An integer
//      * @return: an integer
//      */
    bool getAns(int time, vector<int> &pages, int k) {
        // int tmp = 0;
        // int num = 0;
        // for (int i = 0; i < pages.size(); ++i) {
        //     if (tmp + pages[i] > time) {
        //         tmp = 0;
        //         num++;
        //     } 
        //     tmp += pages[i];
        // }
        // // return num <= k; 还要判断最后一个
        // return tmp <= time && num + 1 <= k;
        
        int tmp = pages[0];
        int num = 1;
        for (int i = 1; i < pages.size(); ++i) {
            if (tmp + pages[i] > time) {
                tmp = 0;
                num++;
            } 
            tmp += pages[i];
        }
        return num <= k;
    }
    int copyBooks(vector<int> &pages, int k) {
        if (pages.empty()) {
            return 0;
        }
        // int low = 1; 会有bug
        int high = 0;
        int maxVal = 0;
        for (int i = 0; i < pages.size(); ++i) {
            high += pages[i];
            if (pages[i] > maxVal) {
                maxVal = pages[i];
            }
        }
        int low = maxVal;
        while (low + 1 < high) {
            int mid = (high - low) / 2 + low;
            if (getAns(mid, pages, k)) {
                high = mid;
            } else {
                low = mid;
            }
        }
        if (getAns(low, pages, k)) {
            return low;
        } else {
            return high;
        }
    }
};